// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class Code02_ReverseNodesInkGroup {
    // 不要提交这个类，这是内部辅助类，用于表示链表节点
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法，用于每k个节点一组翻转链表
    public static ListNode reverseKGroup(ListNode head, int k) {
        // start表示每组的起始节点，初始化为头节点
        ListNode start = head;
        // end表示每组的结束节点，通过teamEnd方法确定
        ListNode end = teamEnd(start, k);
        // 如果end为null，说明剩余节点不足k个，直接返回原链表头节点
        if (end == null) {
            return head;
        }
        // 第一组很特殊，因为这一组的翻转会涉及到链表头节点的改变
        // 将新的头节点设为这一组的结束节点（翻转后这一组的最后一个节点成为新的头）
        head = end;
        // 对第一组节点进行翻转操作
        reverse(start, end);
        // 翻转之后start变成了上一组的结尾节点
        ListNode lastTeamEnd = start;
        // 循环处理后续的组，只要上一组的结尾节点的下一个节点不为空就继续
        while (lastTeamEnd.next!= null) {
            // 确定下一组的起始节点
            start = lastTeamEnd.next;
            // 找到下一组的结束节点
            end = teamEnd(start, k);
            // 如果end为null，说明剩余节点不足k个，直接返回已经处理好的链表头
            if (end == null) {
                return head;
            }
            // 对这一组节点进行翻转操作
            reverse(start, end);
            // 将上一组的结尾节点的next指针指向这一组的结束节点（翻转后这一组的最后一个节点）
            lastTeamEnd.next = end;
            // 更新lastTeamEnd为这一组原来的起始节点（现在的结尾节点）
            lastTeamEnd = start;
        }
        // 返回处理后的链表头节点
        return head;
    }

    // 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
    public static ListNode teamEnd(ListNode s, int k) {
        // 从传入的节点s开始，每次循环减少k的值，直到k为0或者s为null
        while (--k!= 0 && s!= null) {
            // 将s移动到下一个节点
            s = s.next;
        }
        // 返回找到的节点，如果因为节点不足k个而提前退出循环，可能返回null
        return s;
    }

    // s -> a -> b -> c -> e -> 下一组的开始节点
    // 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
    public static void reverse(ListNode s, ListNode e) {
        // 先将e指向它的下一个节点，因为翻转后当前组的最后一个节点要指向它后面的节点（下一组的开始节点）
        e = e.next;
        // pre初始化为null，用于辅助翻转操作，指向当前节点的前一个节点
        ListNode pre = null;
        // cur初始化为当前组的起始节点s，是当前正在处理的节点
        ListNode cur = s;
        // next用于保存当前节点cur的下一个节点
        ListNode next = null;
        // 循环进行节点翻转操作，直到cur到达原来的结束节点e（即翻转后的开始节点的下一个节点）
        while (cur!= e) {
            // 保存当前节点cur的下一个节点
            next = cur.next;
            // 将当前节点cur的next指针指向前一个节点pre，实现翻转
            cur.next = pre;
            // 更新pre为当前节点cur，因为cur的下一个节点翻转后会成为新的cur
            pre = cur;
            // 更新cur为之前保存的下一个节点next
            cur = next;
        }
        // 将原来的起始节点s的next指针指向e，完成这一组节点的翻转
        s.next = e;
    }
}